#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;

/*
unordered_map
*/
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        unordered_map<int, int> mapping;
		vector<int> results;
		for(int i = 0; i < numbers.size(); ++i)
		{
			mapping[numbers[i]] = i;
		}
		for(int i = 0; i < numbers.size(); ++i){
			const int gap = target - numbers[i];
			if(mapping.find(gap) != mapping.end() && mapping[gap] > i)
			{
				results.push_back(i+1);
				results.push_back(mapping[gap]+1);
				break;
			}
		}
		return results;
    }
};


class Solution2 {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i, sum;  
        vector<int> results;  
        map<int, int> hmap;  
        for(i=0; i<numbers.size(); i++){  
            if(!hmap.count(numbers[i])){  
                hmap.insert(pair<int, int>(numbers[i], i));  
            }  
            if(hmap.count(target-numbers[i])){  
                int n=hmap[target-numbers[i]];  
                if(n<i){  
                    results.push_back(n+1);  
                    results.push_back(i+1);  
                    //cout<<n+1<<", "<<i+1<<endl;  
                    return results;  
                }  
  
            }  
        }  
        return results;  
    }
};


int main()
{
	int a[]={1,2,3};
	vector<int> iv(a, a+3), iv2;
	Solution s1;
	iv2 = s1.twoSum(iv, 5);


	system("pause");
	return 0;
}